package factor;

import util.Util;

public class PollardRho {
	private static long f(long x)
	{
		return x * x + 5;
	}
	
	public static long pollardRho(long n)
	{
		long x = 2, y = 2, d = 1;
		while(d == 1)
		{
			x = f(x) % n;
			y = f(f(y) % n) % n;
			d = Util.nzd(Math.abs(x - y), n);
		}
		return d;
	}
	
	public static void main(String[] args) {
		System.out.println(pollardRho(25));
	}
}
